The present invention relates to generally to the field of machine vision, and in particular to a method for efficiently estimating the optical flow between two or more images.
Motion estimation is an important issue which arises in many different machine vision tasks, such as robotics (including navigation and obstacle avoidance), autonomous vehicles, medical image analysis (including nonrigid motion such as angiography), etc. When the motion between two or more generally sequential images is small, it is described by the optical flow defined as the two-dimensional motion field between two different views. The optical flow indicates objects in the image which are moving, where they are moving to and how fast.
Under a constant brightness assumption (xe2x80x9cCBAxe2x80x9d), the pixel motion can be constrained along a single dimension. However, since the flow at a pixel has two components (i.e. orientation (direction and angle) and magnitude (i.e. speed)), optical flow estimation is an inherently difficult problem. Consequently, several attempts have been made to address this problem.
Most prior art methods overcome this problem by xe2x80x9cregularizingxe2x80x9d the flow field, i.e. by enforcing some form of smoothness on the flow field. See K. Horn et al., xe2x80x9cDetermining Optical Flow,xe2x80x9d Artificial Intelligence, Vol. 17, pp. 185-203 (1981); H. Nagel et al., xe2x80x9cOn The Estimation Of Optical Flow: Relations Between Different Approaches And Some New Results,xe2x80x9d Artificial Intelligence, Vol. 33, pp. 299-324 (1987). The CBA can also be cast as an energy minimization, where the flow field is estimated by minimizing the least squares difference between two images. See P. Anandan, xe2x80x9cA Computational Framework And An Algorithm For The Measurement Of Structure From Motion,xe2x80x9d Int""l Journal of Computer Vision, Vol. 2, pp. 283-310 (1989); A. Singh, Optic Flow Computation: A Unified Perspective, IEEE Computer Society Press (1992). Optical flow can also be computed by xe2x80x9cintersectingxe2x80x9d local brightness constraints over a small image patch. See B. Lucas et al., xe2x80x9cAn Iterative Image Registration Technique With An Application To Stereo Vision,xe2x80x9d DARPA IU Workshop, pp. 121-130 (1981). The smoothness problem can also be addressed by fitting a parametric global motion model. See S. Srinivasan et al., xe2x80x9cOptical Flow Using Overlapped Basis Functions For Solving Global Motion Problems,xe2x80x9d Proceedings of European Conference on Computer Vision, Freiburg, Germany, pp. 288-304 (1998).
Many prior art estimation methods achieve a balance between the brightness constraint and smoothness by minimizing a cost function. Since they depend on iterative, non-linear techniques, these methods are not guaranteed to converge to the global minimum and thus give unsatisfactory results when they converge to a local minimum.
The method of the present invention overcomes the above limitations by formulating the problem of flow estimation as a labeling problem in a Markov Random Field (xe2x80x9cMRFxe2x80x9d) framework. Thus, the present invention solves for the dense, non-parametric flow while preserving discontinuities in the flow field.
For certain classes of MRF""s, the exact Maximum A Posteriori (xe2x80x9cMAPxe2x80x9d) estimate can be obtained efficiently by a maximum flow computation on a graph. Being guaranteed to be optimal, this computation avoids the problem of local minima. For examples of some recent methods that use the MRF formulation and a graph-theoretic solution, see: S. Roy et al., xe2x80x9cA Maximum-Flow Formulation Of The n-Camera Stereo Correspondence Problem,xe2x80x9d Int""l Conference on Computer Vision, Mumbai, India, pp. 492-499 (1998); U.S. patent application. Ser. No. 08/978,834, filed Nov. 26, 1997, by S. Roy entitled xe2x80x9cMaximum Flow Method For Stereo Correspondencexe2x80x9d (hereinafter referred to as xe2x80x9cthe ""834 Application,xe2x80x9d and which is hereby incorporated herein by this reference); H. Ishikawa et al., xe2x80x9cOcclusions, Discontinuities, and Epipolar Lines In Stereo,xe2x80x9d Proceedings of European Conference on Computer Vision, Freiburg, Germany, pp. 232-237 (1998); Y. Boykow et al., xe2x80x9cMarkov Random Fields With Efficient Approximations,xe2x80x9d Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 648-655 (1998).
Another significant problem in flow estimation is the computation of image derivatives. Since the image is discretized in the spatial, temporal and intensity dimensions, the accuracy of the discrete computation of spatio-temporal derivatives is limited. This problem is partially addressed by sophisticated derivative filters. In practice, the derivatives are also corrupted due to deviations from the constant brightness assumption such as change of illumination, brightness scaling and specularities. Hence the brightness constraint should not be considered to be a xe2x80x9ctruexe2x80x9d rigid constraint. To capture and account for this notion of uncertainty, the present invention casts the brightness constraint in a probabilistic framework. A related example of a probabilistic interpretation of optical flow is described in an article by E. Simoncelli et al. entitled xe2x80x9cProbability Distributions of Optical Flow,xe2x80x9d in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 310-315 (1991), which overcomes some of the problems of non-probabilistic approaches but suffers in performance from an oversimplistic optical flow model which fails to account for nonlinear characteristics of optical flow probabilities and fails to properly account for errors in image derivatives.
What is needed is a method for estimating optical flow that properly models the errors in the measurement of image derivatives while enforcing the brightness constraint, and which also efficiently provides a globally optimal solution to the optical flow in the context of said model.
Generally speaking, in accordance with the invention, a method for estimating the optical flow between a plurality of images is provided. The method includes obtaining a motion orientation component and a motion magnitude component. Determining the motion orientation component includes creating, a first graph using spatio-temporal derivatives of the plurality of images, solving for a first maximum-flow in the first graph to thereby obtain a first minimum-cut therefrom, and computing the motion orientation component from the first minimum-cut. Determining the motion magnitude component includes creating a second graph using spatio-temporal derivatives of the plurality of images and the motion orientation component, solving for a second maximum-flow in the second graph to thereby obtain a second minimum-cut therefrom, and computing the motion magnitude component from the second minimum-cut. The motion orientation component and the motion magnitude component together comprise the estimate of the optical flow between the plurality of images. The method properly models errors in the measurement of image derivatives while enforcing a brightness constraint, and efficiently provides a globally optimal solution to the optical flow in the context of the model.
Accordingly, an object of the invention is to provide a method for estimating optical flow which efficiently and accurately estimates the optical flow between a plurality of images.
Another object of the invention is to provide a method for estimating optical flow which properly models errors in the measurement of image derivative while enforcing a constant brightness assumption constraint.
A further object of the invention is to provide a method for estimating optical flow which efficiently provides a globally optimal solution to the optical flow in the context of its model.
Other objects of the present invention will become more readily apparent in light of the following description in conjunction with the accompanying drawings.